package leetCode;

import javax.xml.transform.Source;
import java.util.*;

@SuppressWarnings("all")
class ceshi {
    //    public static void main(String[] args) {
//        class mooncake{
//            double store;
//            double totPrice;
//            double unitPrice;
//
//            public double getStore() {
//                return store;
//            }
//
//            public  void setStore(double store) {
//                this.store = store;
//            }
//
//            public double getTotPrice() {
//                return totPrice;
//            }
//
//            public void setTotPrice(double totPrice) {
//                this.totPrice = totPrice;
//            }
//
//            public double getUnitPrice() {
//                return unitPrice;
//            }
//
//            public  void setUnitPrice(double unitPrice) {
//                this.unitPrice = unitPrice;
//            }
//        }
//        int kinds = 0;
//        int need = 0;
//        Scanner sc = new Scanner(System.in);
//        kinds = sc.nextInt();
//        need = sc.nextInt();
//        mooncake[] mo = new mooncake[kinds];
//        int index = 10;
//        for(int i =0;i<kinds;i++){
//            mo[i] = new mooncake();
//            mo[i].setStore(sc.nextDouble());
//        }
//        for(int i =0;i<kinds;i++){
//            mo[i].setTotPrice(sc.nextDouble());
//            mo[i].setUnitPrice(mo[i].getTotPrice()/mo[i].getStore());
//        }
//        Arrays.sort(mo, new Comparator<mooncake>() {
//            @Override
//            public int compare(mooncake o1, mooncake o2) {
//                if(o1.unitPrice < o2.unitPrice){
//                    return 1;
//                }else{
//                    return -1;
//                }
//            }
//        });
//        double sumProfit = 0;
//        for(int i=0;i<kinds;i++){
//            if(mo[i].getStore()>=need){
//                sumProfit+=need*mo[i].getUnitPrice();
//                break;
//            }else{
//                sumProfit+=mo[i].getTotPrice();
//                need-=mo[i].getStore();
//            }
//        }
//        System.out.println(sumProfit);
//    }
    public static void main(String[] args) {
        String s = minWindow("ADOBECODEBANC","ABC");
        System.out.println(s);
//        int i = minDistance("horse", "ros");
//        System.out.println(i);
//        Map<Integer,Integer> map = new HashMap<>();
//        map.put(1,1);
//        map.put(1,map.get(1)-1);
//        System.out.println(map);
//        student stu1 = new student();
//        student stu2 = new student();
//        student stu3 = new student();
//        stu1.age=18;
//        stu1.age=19;
//        stu1.age=20;
//        System.out.println(stu1.age);
//        System.out.println(stu2.age);
//        System.out.println(stu3.age);
//        int[][] arrays = new int[2][3];
//        int[] array ={1,2,3};
//        arrays[0] = array;
    }

    //    public static int[][] merge(int[][] intervals) {
//        int len = intervals.length;
//        Arrays.sort(intervals, new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                if(o2[0] != o1[0]){
//                    return o1[0] - o2[0];
//                }else{
//                    return o1[1] - o2[1];
//                }
//            }
//        });
//        int temp = intervals[0][1];
//        for(int i = 1;i<len;i++){
//            if(intervals[i][0] <=temp){
////                if(intervals[i][0] > intervals[i-1][0]){
////                    intervals[i][0] = intervals[i-1][0];
////                }
//
//                if(intervals[i][1] < intervals[i-1][1]){
//                    intervals[i][1] = intervals[i-1][1];
//                }
//            }
//            temp = intervals[i][1];
//        }
//        int length = 0;
//        int index = 0;
//        for(int i = 0;i<len;i++){
//            if(!flag[i]){
//                length++;
//            }
//        }
//        int[][] res = new int[length][2];
//        for(int i= 0;i<len;i++){
//            if(!flag[i]){
//                res[index] = intervals[i];
//                index++;
//            }
//        }
//        return res;
//    }
    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if (n * m == 0) return n + m;
        int[][] times = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; i++) {
            times[i][0] = i;
        }
        for (int j = 0; j < n + 1; j++) {
            times[0][j] = j;
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                int min_1 = Math.min(times[i - 1][j] + 1, times[i][j - 1] + 1);
                int min_2 = Math.min(min_1, times[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1));
                times[i][j] = min_2;
            }
        }
        return times[m][n];
    }
    public static String minWindow(String s, String t) {
        if(t.length()==1){
            if(s.contains(t)){
                return t;
            }else{
                return "";
            }
        }
        int[] need = new int[128];
        for(int i =0 ;i<t.length();i++){
            char c = t.charAt(i);
            need[c]++;
        }
        int conut = t.length(),start=0,minLen=Integer.MAX_VALUE,r=0,l=0;
        while(r<s.length()){
            char c = s.charAt(r);
            if(need[c]>0) conut--;
            need[c]--;
            if(conut==0){
                while (l<r && need[s.charAt(l)]<0){
                    need[s.charAt(l)]++;
                    l++;
                }
                if(r-l+1<minLen){
                    minLen = r-l+1;
                    start = l;
                }
                need[s.charAt(l)]++;
                l++;
                conut++;
            }
            r++;
        }
        if(minLen<Integer.MAX_VALUE){
            String res = s.substring(start,start+minLen);
            return res;
        }else{
            return "";
        }
    }
}